package com.lw.leetcode.hash.b;

import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * 1590. 使数组和能被 P 整除
 *
 * @author liw
 * @version 1.0
 * @date 2022/3/28 10:18
 */
public class MinSubarray {

    public int minSubarray(int[] nums, int p) {
        int length = nums.length;
        nums[0] = nums[0] % p;
        for (int i = 1; i < length; i++) {
            nums[i] = (nums[i] + nums[i - 1]) % p;
        }
        int n = nums[length - 1];
        if (n == 0) {
            return 0;
        }
        int min = Integer.MAX_VALUE;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        for (int i = 0; i < length; i++) {
            int v = nums[i];
            Integer c = map.get(v >= n ? v - n : v + p - n);
            if (c != null) {
                min = Math.min(min, i - c);
            }
            map.put(v, i);
        }
        if (min >= length) {
            return -1;
        }
        return min;
    }

}
